#include "common.h"
/* 
单链表la，lb中的元素按照非递减排列，
设计算法归并la，lb得到新的链表lc，且lc中的元素也按照非递减排列
 */

void merge(linklist &la, linklist &lb, linklist &lc)
{
    lnode *pa = la->next, *pb = lb->next;
    // 将la的头结点作为lc的头结点
    lc = la;
    // pc初始指向lc的头结点
    lnode *pc = lc;
    while (pa && pb)
    {
        // a，b都没有到表尾
        if (pa->data <= pb->data)
        {
            // 如果a的值小，则将a插入c
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            // 否则b比a小，则将b插入c
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    // 非空的链表即较长的链表插入到c中
    pc->next = pa ? pa : pb;
    // 实测这里释放b的话会造成异常
    // delete pb;
}
int main(int argc, char const *argv[])
{
    int a[] = {2, 4, 6, 8}, b[] = {1, 3, 5, 7, 9};
    linklist la, lb, lc;
    makelist(la, a, sizeof(a) / sizeof(int));
    printlist(la);
    makelist(lb, b, sizeof(b) / sizeof(int));
    printlist(lb);
    merge(la, lb, lc);
    printlist(lc);
    return 0;
}
